// =====================================================================================
// 
//       Filename:  get_sentence.cpp
// 
//    Description: http://www.careercup.com/question?id=14951746 
// 
//        Version:  1.0
//        Created:  02/03/2013 20:11:38
//       Revision:  none
//       Compiler:  g++
// 
// =====================================================================================

#include <string>
#include <iostream>
#include <set>
#include <vector>
using namespace std;

template<typename T>
void dump(T &a) {
	for(typename T::const_iterator it = a.begin(); it != a.end(); ++it)
		cout<<"-> "<<*it<<endl;
}

bool print_sentence(vector<size_t>  *len, string text, size_t i)
{
	int tmp = i;
	//cout<<"--> "<<tmp<<endl;
	if(tmp < 0) return true;

	vector<size_t> & lens = len[tmp];
	for(int j = 0; j < lens.size(); ++j)
	{
		if(print_sentence(len, text, i - lens[j]))
		{
			cout<<text.substr(i - lens[j] + 1, lens[j]) + " ";
			return true;
		}
	}

	return false;
}

bool get_sentence(string text, set<string> dict)
{
	size_t n = text.length();
	vector<bool> tracer;
	vector<size_t> len[n];
	for(int i = 0; i < n; ++i) {
		tracer.push_back(false);
	}
	for(int i = 1; i < n; ++i)
	{
		if(dict.find(text.substr(0,i)) != dict.end()){
			tracer[i-1] = true;
			len[i-1].push_back(i);
			//cout<<text.substr(0, i) + " is a word"<<endl;
		}
		else {
			for(int j = 0; j <i; ++j) {
				//if(tracer[j]) cout<<"==> " + text.substr(j+1, i -j)<<endl;
				if(tracer[j] && dict.find(text.substr(j+1, i-j)) != dict.end()) {
					tracer[i] = true;
					len[i].push_back(i-j);
					//cout<<text.substr(j+1, i - j) + " is a word"<<endl;
					break;
				}
			}
		}
	}

	/*
	for (int i = 0; i < n; i++) {
		cout<<"dumping: "<<i<<endl;
		dump(len[i]);
	}  */
	
	if(tracer[n-1]) {
		if(print_sentence(len, text, n - 1))
			cout<<endl;
		return true;
	}
	return false;
}

int main(int argc, const char *argv[])
{
	set<string> dict;
	dict.insert("from");
	dict.insert("waterloo"); 
	dict.insert("hi");
	dict.insert("am");
	dict.insert("yes");
	dict.insert("i");
	dict.insert("a");
	dict.insert("student");
	string s = "iamastudentfromwaterloo";
	string s1 = "hifromwaterloo";
	string s2 = "hifromcalifornia";

	dump(dict);

	cout<<"Testing: " + s<<endl;
	string r= get_sentence(s, dict) ? "True" : "False";
	cout<<r<<endl;

	cout<<"Testing: " + s1<<endl;
	r= get_sentence(s1, dict) ? "True" : "False";
	cout<<r<<endl;

	cout<<"Testing: " + s2<<endl;
	r= get_sentence(s2, dict) ? "True" : "False";
	cout<<r<<endl;
	return 0;
}
